%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% TODO
%
% >>>> Partie Spécifications -> Gestion des Salons -> Algorithmes d'élections
%		que ceux qui ont mis en place l'ago de "centre et second" avec les identifiant du genre "1.2.3.4" (Mathieu et Gael je crois) détaillent, si possible à mort avec graph et expli du pour et du contre des autres technique et pourquoi avoir retenu celle là. Histoire que l'on nous ressorte pas "encore une fois" qu'on aurai pu faire de la topo bien lourde avec dijkstra et tout ça
%
% >>>> Partie Algorithmes
%		Copé collé du wiki, à commenter par les gens qui les ont postés sur le wiki
%		revoir les algos pour vérif que c'est bien la dernière version, (bien qu'ils aient du être fait après vérouillage de la prog) et remplacer les "?". Eviter les noms de variable style code "var_toto" et utiliser un maximum de msg[i], msg[j], message bleu, rouge et autres conventions qui, bien que intuitives et super claires, sont utilisées en masse par notre cher corps professoral
%
% >>>> Partie Développement -> Détail de chaque module -> Interface
%		A remplir, screens, détails, fonctionnement, commandes, exemples
%		Virer tk si tile est développé
%
% >>>> Contribuer à l'intro et surtout la conclusion
%
% >>>> Relecture et validation de tous les membres (prévenir en cas de changement majeur)
% +    + Guillaume
% +    + Pierre-Yves
% +    + Mickael
% +    + Bruno
% +    + Gael
% +    + Mathieu
%
% Notes:
%		Pour les schémas, gimp fait de la conversion png ou autre en eps
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[10pt,a4paper]{report}

%\usepackage[top=2cm, bottom=2cm, left=3cm , right=3cm]{geometry}

\RequirePackage{fancyhdr,vmargin}
\usepackage{graphicx}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{style}
\usepackage{indentfirst}

\fancypagestyle{plain}{
	\fancyhf{}
	\fancyfoot{}
	\fancyfoot[R]{\thepage}
	\fancyfoot[L]{G. Kania, P.-Y. Lozachmeur, M. Magniez, B. Sabos, G. Tremeau, M. Gaspard}
	\fancyhead[L]{SR05 - Application de discussion dans un réseau fortement dynamique} 
	\fancyhead[R]{\includegraphics[height=0.5cm]{images/utc.eps}}
} 
\fancyhf{}
\fancyfoot{}
\fancyfoot[R]{\thepage}
\fancyfoot[L]{G. Kania, P.-Y. Lozachmeur, M. Magniez, B. Sabos, G. Tremeau, M. Gaspard}
\fancyhead[L]{SR05 - Application de discussions dans un réseau fortement dynamique}
\fancyhead[R]{\includegraphics[height=0.5cm]{images/utc.eps}}
\pagestyle{fancy}

\newcommand{\p}{\par \vspace{0.5cm}}
\newcommand{\si}{\hspace*{1cm}}

\newenvironment{listeactions}%
{ \begin{list}%
	{$\bullet$}%
	{\setlength{\labelwidth}{30pt}%
	 \setlength{\leftmargin}{35pt}%
	 \setlength{\itemsep}{\parsep}}}%
{ \end{list} }
%\itemsep

\begin{document}
\title{SR05 - Application de discussions dans un réseau fortement dynamique}
\author{Guillaume Kania,\\Pierre-Yves Lozachmeur,\\Mickael Magniez,\\Bruno Sabos,\\Gael Tremeau,\\Mathieu Gaspard}
\maketitle
\setcounter{tocdepth}{4} % Profondeur du sommaire
\setcounter{secnumdepth}{2} % Profondeur de numération des sections
\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Introduction
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Introduction}
Ce projet s'inscrit dans le cadre de l'UV SR05 et a pour objectif d'appréhender les problèmes de communications et de synchronisations entre plusieurs entités dans un réseau fortement dynamique o\`{u} l'on a, à priori, aucune idée de la topologie ni même de la présence de voisins.
\p
Le sujet retenu est une application de discussions organisées en salons qu'il est possible de créer ou de rejoindre librement. La seule condition à respecter est d'être à portée du centre du salon, c'est à dire le créateur ou l'actuel leader du salon (lorsque que le créateur a disparu).
\p
Ce type de programme nécessite une détection de ses voisins, une synchronisation, une propagation et une retransmission des messages ainsi q'une gestion de distance point à point. Afin de ne pas surchager le réseau, un effort doit être apporté lors de la propagation et de la retransmission des messages ainsi que pour les messages de présence de salon pour ne pas émettre de messages inutiles ou redondants.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Spécifications
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Spécifications}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Définitions
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\section{Définitions}
\begin{listeactions}
	\item Noeud: Représente une entité du réseau, un client du service de discussion ou une voiture et indirectement un utilisateur
	\item Centre: Créateur d'un salon, appelé centre car il est la référence du calcul de la distance, en temps de transfert, de chaque participant
\end{listeactions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Interface
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\section{Interface}
L'interface est divisée en 5 parties (5 frames):
\begin{listeactions}
	\item Liste des salons: Cette partie contient la liste des salons accessibles. On peut se connecter à un salon en cliquant dessus.
	\item Liste des utilisateurs: C'est ici que l'on trouve la liste des utilisateurs connectés au salon courant. Aucune interaction n'est prévue dans cette liste.
	\item Liste des onglets et partie affichage des messages: C'est la partie centrale de l'interface, elle contient d'abord une liste des salons auquels on est connecté (via une liste d'onglets, l'onglet actif détermine le salon courant). De plus, à chaque onglet est associé la liste des messages échangés depuis la connexion au salon.
	\item Zone de saisie: C'est ici que sont saisis les messages que l'utilisateur veut envoyer sur le salon courant. En entrant /help on a accès à la liste des commandes disponibles.
	\item Partie debug: Cette partie n'est utile que pendant les phases de développement, elle contient actuellement des informations sur les voisins directs (elle est cependant susceptible d'afficher d'autres types d'informations selon les besoins des développeurs). Il existe aussi une fenêtre debug qui permet aux développeurs d'afficher des informations de deboguage et surtout, d'en garder un historique.
\end{listeactions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Gestion des messages
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\section{Gestion des messages}
			\subsection{Recevoir un message}
La réception d'un message (dit de type "message") permet de mettre à jour ses infomations sur l'état du noeud émetteur mais également sur l'état des autres noeuds du salon. En effet, ces messages contiennent l'horloge vectorielle distante indiquant la vision de l'état du salon selon le noeud émetteur, qui peut être plus récente que la notre.
			\subsection{Envoyer un message}
Le texte à transmettre aux participants du salon est accompagné de l'horologe vectorielle locale précisant la vision que l'on a de l'état de ses voisins et des informations utiles sur le centre du salon, puis diffusé en aveugle à ses voisins.
			\subsection{Propager un message}
Les messages contiennent l'identifiant du centre du salon dans lequel ils doivent être propagés. Les noeuds connaissant leur distance par rapport à ce noeud, il peuvent savoir s'il sont en dehors de la portée prédéfinie du salon et s'il doivent rediffuser le message. C'est ainsi que le message ne peut dépasser, au maximum, les frontières définies par sa portée paramétrée + la portée d'un noeud qui se situerait juste en frontière de cette zone.
\p
Afin de soulager le réseau des messages redondants, un noeud ne retransmet un message que s'il reste au moins un de ses voisins directs qui ne l'a pas encore reçu. De plus, lorsqu'un noeud transmet ou retransmet un message, il indique "par anticipation" que ses voisins directs l'on reçu. Ces deux principes allègent énormément le réseau sans que cela nuise à la bonne transmission des messages.
\p
Notons qu'un noeud qui ne participe pas au salon peut retransmettre tout types de messages.
			\subsection{Demander un rectificatif ou un complément d'informations}
Lorsqu'un noeud constate par la comparaison de son horloge vectorielle locale avec les horloges distantes transmises avec les messages de ses voisins qu'il lui manque des messages, il envoie une requête de retransmission de ces messages manquants (avec identifiant du salon, identifiant du noeud émetteur et numéro d'action associé au message manquant). Cette requête est propagée dans tout le salon un nombre paramétré de fois avant abandon. Un noeud recevant une requête de retransmission contenant plusieurs identifiant de message manquants, allège la requête des messages auxquels il peut répondre avant de retransmettre les requêtes restantes aux autres noeuds du réseau. Ainsi, si ses voisins directs ont la réponse, le message ne va pas plus loin qu'un saut. Enfin, les noeuds intermédiaires profitent des requêtes pour mettre à jour leurs horloges vectorielles respectives et leurs historiques de messages respectifs.


			\subsection{Ordonnancement chronologique des messages}
Dans un réseau fortement dynamique, la question de l'ordonnancement des messages est un problème majeur. En effet, les horloges vectorielles permettent d'établir qu'un ordre partiel des messages reçus, ce qui n'est pas acceptable dans une application de type discussion.
\p
Afin de respecter la chronologie des messages envoyés (notamment dans le cas des questions-réponses), un ordonnacement par estampille sera utilisé.
\p
La chronologie n'étant importante qu'à l'intérieur d'un salon donné, chaque salon possèdera sa propre estampille.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Gestion de son evironnement
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\section{Gestion de son environnement}
			\subsection{Signaler sa présence et connaître ses voisins}
Afin qu'un noeud puisse détecter la présence de ses voisins directs, il est nécessaire que chaque noeud émette à intervalles de temps réguliers un signal de présence, qu’il soit connecté à un salon ou non. Ils utilisent pour cela des messages de type "ping"

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Gestion des distances
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\section{Gestion des distances}
Un noeud se signale régulièrement par des messages de type "ping" auprès de ses voisins directs qui lui répondent immédiatement. Les noeuds peuvent donc savoir à quelle distance (en temps) se situent leurs voisins directs.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Gestion des salons
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\section{Gestion des salons}
			\subsection{Taille maximale d'un salon}
Plusieurs solutions étaient envisageables pour déterminer la taille maximale d'un salon
\begin{listeactions}
	\item La distance d'un point de vue géographique en utilisant les données GPS : nécessite la présence et la disponibilité en continue de récepteurs GPS. En plus de limiter le nombre d'utilisateurs potentiels, la métrique utilisée n'est pas représentative des conditions optimales de transmission des messages. Ce n'est pas parce qu'un noeud est proche géographiquement du centre qu'il est forcément capable de lui répondre en un temps raisonable (il peut en effet être surchargé par une activité qui ne dépend même pas de l'application). Il déséquilibrerait donc le réseau (création de bouchon) en retardant tous les messages pour les noeuds qui l'utiliseraient comme passerelle et génèrerait donc des problèmes de synchronisations ainsi qu'un nombre important de messages de retransmission, etc...\\

	\item Le nombre de sauts effectués pour transférer le message : chaque noeud sait combien de sauts ses messages doivent effectuer pour communiquer avec le centre du salon. Meilleure que la première solution, elle garde tout de même le problème d'un déséquilibre important en réactivité d'un noeud à l'autre du salon\\

	\item Le temps de transit du message : par l'intermédiaire des pings, les noeuds connaissent leur distance en temps par rapport à leur voisins immédiats, la distance par rapport au centre peut donc être calculée en additionnant les distances lors de chaque retransmission. C'est la solution retenue car elle ne demande pas la présence d'un récepteur GPS et permet de garder un salon équilibré autour du centre.
\end{listeactions}

			\subsection{Créer un salon}
Quand un noeud veut créer un salon, il choisit un nom pour celui-ci, il sera utilisé (avec l'id du noeud) pour identifier ce salon.
\p
Après cette création et tant que le salon existe, le noeud signale régulièrement sa présence à tous les noeuds à portée (dans le sens de portée maximale d'un salon) en envoyant un message de type salon (qui sera donc retransmis dans tout le rayon d'existence du salon).

			\subsection{Distance au centre d'un salon}
Le centre d'un salon émet régulièrement un message de présence de ce salon en commençant avec une distance égale à 0. A chaque saut, les noeuds intermédiaires ajoutent à cette distance la distance par rapport au noeud intermédiaire précédent puis retransmettent le message si cette distance est inférieure à la portée précédemment fixée du salon. Chaque noeud intermédiaire connait ainsi sa distance par rapport au centre du salon
\p
Rappelons que la distance de proche en proche est connue grâce aux pings réguliers.
			\subsection{Détecter des salons}
				\subsubsection{Détecter les participants}
Là encore, différentes solutions ont possibles:
\begin{listeactions}
\item Solution 1: Quand un noeud veut connaître la liste des participants à un salon, il en fait la demande à tous ses liens directs. Si le noeud qui reçoit la demande participe au salon, il répond, sinon, il retransmet.\\
\si
La liste des participants devant être régulèrement mise à jour, cette solution nécessite que le noeud émette régulièrement une demande de la liste des participants. Cela entraine beaucoup de réponses redondantes et un problème de synchronisation puisque les noeuds répondant à la requête ne possèdent pas forcément une liste à jour.\\
\si
Afin d'éviter les messages redondants, les noeuds recevant de telles demandes pourraient attendre un temps aléatoire avant de répondre, et si un autre noeud a répondu dans l'intervalle, ne pas envoyer la liste (un peu comme l'algorithme de backoff dans ethernet). On perd alors en réactivité jusqu'à quelques secondes au pire.\\

\item Solution 2: Les noeuds participants au salon se signalent régulièrement. La liste des participants sera construite au fur et à mesure (dans un temps acceptable inférieur à 1s).\\
\si
Cette solution supprime le problème des réponses redondantes et enlève le problème des demandes inutiles de la deuxième solution. En effet, puisque les listes des participants doivent être régulièrement mises à jour, tous les noeuds devront envoyer des demandes fréquemment. Les demandes étant prévisibles, elles ne sont pas nécessaires et il suffit d'envoyer la "réponse" régulièrement afin que tout le monde en profite.
\end{listeactions}
				\subsubsection{Détecter un nouveau participant}
Quand un noeud rejoint un salon, il commence par envoyer un message de présence à l'ensemble des participants qui ont donc maintenant conscience de la présence de ce noeud dans le salon.

				\subsubsection{Détecter la déconnexion d'un participant}
Régulièrement le noeud envoie un message de type salon (retransmis) pour signaler qu'il est toujours connecté au salon. Après chaque réception d'un message de présence, un timeout est enclenché. Lorsque ce timeout expire, le noeud est considéré comme déconnecté.

			\subsection{Rejoindre un salon}
Un noeud ne voit que les salons auquels il peut participer, même si l'application peut avoir connaissance de salons dont elle est à presque à portée. Il ne rejoint un salon qu'en commençant à envoyer des messages de présence à ce salon.

			\subsection{Quitter un salon}
				\subsubsection{Volontairement}
Côté application, il suffit de fermer la fenêtre affichant les messages du salon. Les autres participants prendront connaissance de cette déconnexion après expiration du timeout associé à la réception des messages de présence.

				\subsubsection{Involontairement (déconnexion, éloignement)}
Si le noeud se trouve trop loin du centre, il ne peut plus communiquer à l'intérieur et doit se rapprocher du centre ou recréer un nouveau salon. Comme pour la déconnexion volontaire, les participants du salon que le noeud vient de quitter ne percoivent plus ses messages de présence et le considèrent après timeout comme déconnecté. (Cependant le noeud est susceptible de "recréer" le salon comme nous l'expliquerons plus tard lors de la présentation de l'algorithme d'élection).

				\subsubsection{Fermeture du salon}
					\paragraph{Le leader ferme volontairement le salon}
Si le leader ferme le salon (fermeture du salon, arrêt de l'application), un nouveau centre est défini selon l'algorithme d'élection choisi. Le salon garde toutes ses caractéristiques : nom, membres et messages.

					\paragraph{La personne est trop loin du centre}
Si un noeud ou un groupe de noeud se retrouve trop éloigné du centre du salon pour en faire partie, ils sont déconnectés, et doivent se rapprocher du centre du salon pour de nouveau y avoir accès. (Cependant le ou les noeuds sont susceptibles de "recréer" le salon comme nous l'expliquerons plus tard lors de la présentation de l'algorithme d'élection).


\newpage
			\subsection{Algorithmes d'élection}
Lors de la disparition d’un centre de salon due à une déconnexion ou à un éloignement trop important du reste du salon, les messages d'existence du salon ne sont plus retransmis entre les nœuds (puisque le noeud centre est hors de portée ou déconnecté) et le salon disparaît. Il était important de mettre en place un système qui permettait la nomination d’un nouveau centre et d'assurer ainsi la pérennité du salon malgré les possibles déconnexions du centre du salon.
\p
L’application évoluant dans une topologie particulièrement changeante, il ne nous a pas été facile  de choisir un algorithme pour désigner un centre qui remplacera le premier lors de sa déconnexion. Les choix que nous exposons sont avant tout pragmatiques, ils présentent certaines qualités mais aussi de nombreux défauts. Voici les deux solutions qui nous ont semblées viables:\p
\begin{itemize}{}{}
\item Un algorithme d’élection déclenché à la déconnexion, ainsi le centre élu pourra être placé efficacement au centre géographique du salon. Par contre ce système est lourd à mettre en place à cause de la topologie changeante du réseau ; les vagues à diffuser (pour renseigner les nœuds, les mettre d’accord et en désigner un) peuvent échouer, il faut donc mettre de nombreux timouts qui devront redémarrer les vagues. Le risque de saturation est donc très important.
\item Un algorithme de nomination explicite d’un centre suppléant par le centre du salon. Ce centre suppléant deviendra actif  à la disparition du centre. Ce système est extrêmement simple à mettre en place. Le centre du salon nomme un nouveau centre suppléant à chaque emission d'un message de type salon (il le sélectionne en prenant le noeud le plus proche parmi les noeuds connectés au salon) et lui donne un poids (incrémenté à chaque fois). Ainsi c'est la nature même de la topologie (changeante, donc le noeud connecté le plus proche n'est jamais le même) qui va permettre de répartir les poids. Tous les noeuds connectés sont donc susceptibles d'avoir un poids. Ensuite chaque noeud lance un timeout différent selon sa distance au centre (plus il est loin et plus le timeout est élevé). Si dans l'intervalle de ce timeout le noeud reçoit un message de type salon, il réenclenche le timeout, autrement le noeud considère qu'il peut prendre le pouvoir et devenir centre du salon (puisque personne ne se manifeste). L'avantage de cette solution est que ce sont les noeuds proches du centre lorsque celui-ci est tombé (déconnexion ou défaillance) qui vont se manifester d'abord. Ils vont envoyer des demi-vagues avec leurs poids respectifs, la vague la plus lourde éteint les autres demi-vagues. L'efficacité de cet algorithme repose sur le double avantage que l'on donne aux noeuds proches du centre (leur poids est élevé et ils se manifestent avant)
\end{itemize}
\p Cependant, le choix d’un nouveau centre pourra quand même rendre certains nœuds trop éloignés du centre du salon et ils ne feront donc plus partie du salon (ils ne seront pas atteints par les demi-vagues de prise de pouvoir). Mais, dans ces cas là, si ces noeuds ont un poids (c'est-à-dire s'il ont été proches de l'ancien centre) ils vont prendre le pouvoir puisque leur timeout d'attente de messages de type salon arrivera à 0. Les salons peuvent donc se diviser. L'inconvénient majeur, que nous n'avons pas réussi à résoudre, est qu'en cas de regroupement des deux versions du salon, on augmente le périmètre maximal du salon (puisque on ne veut pas différencier les deux centres existants). Un salon peut donc devenir infini. C'est un inconvénient majeur sur lequel nous réflechissons encore (changement de l'id du salon en cas de division).
\p
Notre choix s’est porté sur la seconde solution car la première nous semblait trop complexe à réaliser. Nous pensons qu’il valait mieux un algorithme de nomination avec des défauts qui puisse entraîner la division du salon, qu’un algorithme d’élection qui converge en un temps inconnu (ce temps pouvant être très long dans le cas d'un réseau mouvant, à la topologie changeante et, en plus, hautement dynamique).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Développement
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Développement}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Schéma de fonctionnement général
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\section{Schéma de fonctionnement général}
\begin{center}
	\rotatebox{0}{\includegraphics[width=15cm]{images/Schema_general.eps}}\\
\end{center}

L'application est découpée en 4 modules séparant les données et fonctions selon leur rapport à la gestion de l'interface, la manipulation des informations de session, la gestion de l'environnement (voisins, salons, ...) et les communications avec les autres applications.
\p
Comme indiqué sur le schéma (avec les flèches "CALL"), les parties respectent au maximum la structure "en pile" et ne communiquent qu'avec les couches voisines. Ainsi, l'interface n'intervient en aucun cas sur les communications inter-applications et, inversement, la couche communications ne modifie pas directement les informations de session.
\p
Aucune partie ne peut intervenir directement sur les données des autres parties et elles peuvent s'apparenter à des classes utilisées en programmation orientée objet dont l'ensemble des membres et méthodes sont privés. Seuls restent publiques les accesseurs et les appels de services.
\p
Les prototypes des accesseurs constituant les interfaces inter-couches doivent évidemment être identiques quelque soit le choix d'implémentation de chaque couche. L'interface, lancée par le coeur de l'application, peut cependant demander une gestion particulière ou l'initialisation d'un environnement spécifique. Pour cela, le coeur utilise le "front-end" dont les prototypes sont communs à n'importe quel type d'interface et dont les corps peuvent être adaptés à n'importe quelle situation. C'est lui qui se chargera d'initialiser l'interface et fera le lien avec le coeur.
\p
Dans le cadre de notre projet, cette méthode de séparation des éléments constitutifs du projet n'a pas réellement pour but premier de pouvoir jongler avec différents modules, mais clarifie les idées et propose une organisation facilement "maintenable" et évolutive.
\p
L'arborescence fichiers du projet suit naturellement cette même structure. A chaque partie correspond un répertoire du même nom. Le coeur se compose en plus de sous-répertoires permettant de grouper les fonctions selon des "thèmes" plus fins comme la gestion spécifique des salons, le voisinage, la synchronisation des messages, ...
\begin{center}
	\rotatebox{0}{\includegraphics[width=15cm]{images/dirAndFile.eps}}\\
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Détail de chaque module
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
		\section{Détail de chaque module}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Instance
			\subsection{Instance}
Avant de nous intéresser aux algorithmes de gestion du chat, nous allons détailler les structures de données manipulées pour stocker les différentes informations uniques à une session de l'application, appelée ici "Instance".
\p
A chaque information est associée un ensemble d'accesseurs permettant d'ajouter, modifier, supprimer ou lire les données et c'est cette couche elle-même qui se charge de formater les données demandées sous une structure précise, les informations pouvant être stockées sous différentes formes et sur différents supports (imaginons une base de données, un simple fichier texte, ...).
\p
L'instance regroupe ainsi les informations sur l'utilisateur comme son pseudo, les salons auxquels il participe et ceux dont il est le centre, la liste de ses voisins et des contacts qu'il a récemment "vu", ...

				\subsubsection{Informations personnelles}
Les seules informations personnelles nécessaires pour cette application sont un identifiant unique et un pseudo

				\subsubsection{Données sur les noeuds connus dans le réseau}
Mémorise la liste des noeuds dont on a déjà reçu l'identifiant (dans un message de type "ping", de type "message" ou de présence dans un salon) associés a leurs pseudos (récupérés dans les messages de présence dans un salon).
\p
\begin{center}
	\rotatebox{0}{\includegraphics[width=6cm]{images/ListeNoeuds.eps}}\\
\end{center}

				\subsubsection{Liste des voisins directs}
Contient la liste des noeuds qui sont directement à portée des périphériques de communication. Sont mémorisées la distance par rapport à ce noeud (calculée avec les pings) et la date du dernier contact.
\p
\begin{center}
	\rotatebox{0}{\includegraphics[width=8cm]{images/ListeVoisins.eps}}\\
\end{center}
				\subsubsection{Liste des salons détectés (dont ceux auxquels participe l'utilisateur)}
Cette section contient des informations sur
\begin{listeactions}
	\item \textbf{L'identifiant du salon dans lequel l'utilisateur discute actuellement}
	\item \textbf{La liste des salons détectés avec pour chacun:}
		\si L'identifiant du salon\\
		\si Le nom du salon\\
		\si La liste des noeuds distants connectés à ce salon\\
		\si L'identifiant du noeud étant le centre du salon\\
		\si La date de dernier contact au salon\\
		\si La distance en temps par rapport au centre du salon\\
		\si L'identifiant de dernier ping utilisé pour ce salon\\
		\si La liste des messages manquants\\
		\si Et un flag signalant la participation de l'utilisateur au salon\\
	\item \textbf{Un paramètre précisant le nombre de demandes de retransmission avant abandon des messages manquants}
\end{listeactions}
\begin{center}
	\rotatebox{0}{\includegraphics[width=15cm]{images/ListeSalons.eps}}\\
\end{center}

				\subsubsection{Horloge vectorielle}
\begin{listeactions}
	\item \textbf{l'horloge vectorielle locale} contient trois champs
		\si Un identifiant de salon ...\\
		\si ... et l'identifiant d'un noeud distant participant à ce salon\\
		\si Le dernier numéro d'action du noeud distant\\
\end{listeactions}
Les deux premiers champs peuvent être assimilés à une clef binaire donnant comme information utile le dernier numéro d'action du contact.
%Cette horloge permet de connaître l'état des noeuds distants et de savoir si on a manqué des messages
\p
Cette horloge permet de mémoriser notre vision de l'état des noeuds distants. Par comparaison avec les horloges distantes transmises avec les messages de type "message" ou "ping", elle permet de savoir si un message a déjà été reçu et de détecter les messages manqués.
\begin{center}
	\rotatebox{0}{\includegraphics[width=8cm]{images/horloge.eps}}\\
\end{center}

				\subsubsection{Liste des messages reçus}
Stocke pour chaque salon, la liste des couples: messages et identifiant du noeud émetteur.
\begin{center}
	\rotatebox{0}{\includegraphics[width=9cm]{images/ListeMessages.eps}}\\
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Core
	\subsection{Core}
		\subsubsection{Fonctionnement de la propagation}
			\paragraph{Propagation dans un salon}
La gestion de la propagation repose sur deux champs. Le permier renseigne sur les noeuds participant au salon dans lequel on veut propager le message et le deuxième mémorise les noeuds par lesquels le message est déjà passé. A chaque fois qu'un noeud participant au salon reçoit le message, il se supprime de la liste du premier champ et s'ajoute à la liste du dexième champ. Lorsque la première liste est vide ou que la distance au centre est supérieur à la portée du salon, la propagation s'arrête.
\p
Ainsi, un noeud émetteur enverra son message avec le premier champ remplit des participants au salon sauf son propre identifiant et la deuxième contenant uniquement son identifiant.
\p
Un noeud intermédiaire ne participant pas au salon ne change pas le premier champ, mais s'ajoute également au deuxième champ.
\p
Afin de soulager le réseau, lorsque un noeud reçoit un message à propager, il ajoute directement ses voisins directs à la liste des noeuds ayant déjà reçu le message. Il considère ainsi par anticipation que ses voisins vont le recevoir. Cela évite que ses voisins directs s'envoient ensuite entre eux ce même message, puisqu'il viennent de le recevoir ensemble.
\p
\begin{center}
	\rotatebox{0}{\includegraphics[width=12cm]{images/propagation.eps}}\\
\end{center}
\p
Détail supplémentaire: on voit dans le cas (B) que le noeud "b" retourne (involontairement) le message à "a".
\begin{listeactions}
	\item Soit "a" retraite l'information, pour profiter des informations que "b" a pu ajouter au message. "a" peut profiter d'un message de tout façon envoyé par "b" pour mettre à jour son horloge vectorielle.
	\item Soit "a" considère ne pas avoir d'information nouvelle à retirer du message de "b". C'est le cas des messages de signalisation de salon. Dans ce cas, un identifiant de dernier ping salon est utilisé pour éviter de retraiter le messages. Il ne peut en effet pas regarder dans le deuxième champ puisqu'il ne peut pas différencier le cas où il est présent par anticipation du cas où il est présent parce qu'il l'a déjà reçu.
\end{listeactions}
\p
Ainsi, même si l'environnement du salon contient un nombre important de noeuds partipant ou non, la charge réseau reste relativement faible.
\p
Cette technique a pour avantage d'avoir un premier champ relativement fixe au départ qui correspond aux participants, quelque soit le nombre de noeuds servant de passerelle. De plus, si un noeud, participant ou non, apparait au cours de la propagation du message alors qu'il n'était connu d'aucun autre noeud au moment où il reçoit le message, il ne change en rien le déroulement de la propagation. Il va juste s'ajouter au deuxième champ et retransmettre le message. Au pire (c'est à dire qu'il ne connait pas ses voisins directs), seul un message redondant sera envoyé.
			\paragraph{Propagation dans un périmètre}
La propagation dans d'un message dans la portée maximale d'un salon est identique à la propagation dans un salon donné à cela que le premier champ est vide. Ainsi le message est retransmis jusqu'au frontière de la portée sans vérifier ce premier champ.
		\subsubsection{Salons}
			\paragraph{Création d'un salon}
Chaque noeud peut créé un nouveau salon. Pour cela, il choisit un nom à lui donner (constitué uniquement de caractères alphanumériques ou d'espaces). Ce nom sera celui présenté aux utilisateurs dans l'interface mais n'est pas utilisé pour l'identification du message. Un identifiant "artificiel" est créé à partir du nom donné au salon et de l'id du noeud créateur, par exemple si le noeud "Noeud" créé un salon qu'il nomme "Salon" l'id sera le suivant :
\si Salon\#Noeud
			\paragraph{Détection d'un salon}
Une fois le salon créé, le noeud broadcast un message de présence de ce salon à tous ses voisins sous forme d'une demi vague qui se propage juqu'a ce que la distance de propagation soit supérieur à la taille limite prédéfinie.
\p
En pratique, la création d'un salon n'entraîne pas sa signalisation immédiatement, un "démon" se charge d'envoyer à intervalle régulier la liste des salons. Ce démon parcours donc la liste de tous les salons connus du noeud, et si il s'avère qu'il en est le créateur, il l'ajoute à la liste des salon à signaler. Pour chaque salon, on envoie non seulement son id mais également son nom. L'identifiant du créateur est également inclus dans le message. Par exemple, pour un noeud a crééant N salons S1, S2, ..., SN, le message envoyé sera :
\p
\begin{center}
\begin{tabular}{lc}
	%\hline
	\textbf{Champ} & \textbf{Exemple}\\ \hline
	type de message (10=salon) & 10\\ %\hline
	id du noeud émetteur/retransmetteur & a\\ %\hline
	id du centre du salon, donc l'id du noeud émetteur & a\\ %\hline
	distance du centre, initialement à 0 & 254\\ %\hline
	salons associés au centre (id du salon et id du centre) & S1\#a,Salon1\\ %\hline
	... & S2\#a,Salon2\\ %\hline
	... & ...\\ %\hline
	... & SN\#a,SalonN\\ %\hline
	champs de gestion de la propagation & propagation\\ %\hline
	horloge vectorielle & horloge\\
	%\hline
\end{tabular}
\end{center}
\p Ce qui donne sous forme de chaine:
\si $10|a|a|0|S1\#a,Salon1:S2\#a,Salon2:...:SN\#a,SalonN|propagation|horloge$
\p
Ce message sera donc reçu par tous ses voisins directs. Quand un noeud reçoit un message de ce type, il commence par vérifier qu'il ne l'a pas déjà reçu gràce à l'horloge vectorielle. Dans ce cas, il regarde si le noeud lui retransmettant le message lui est connu et si tel est le cas, il ajoute la distance par rapport à ce voisin à la distance totale représentant l'éloignement du centre du salon. Il extrait alors la liste des salons (paires identifiant/nom) contenus dans le message et pour chacun d'entre eux :
\p
\begin{listeactions}
	\item Si il ne le connaissait pas encore, vérifie si la distance précédemment calculée est inférieure à la portée maximale d'un salon et dans le cas positif, ajoute le salon à sa liste locale.
	\item Si il le connaissait déjà, il met à jour la distance et la date de dernier contact, vérifie que cette distance est toutjours correcte, dans le cas contraire, il supprime le salon de la liste locale après avoir éventuellent déconnecté le noeud. 
\end{listeactions}
\p
En fontion du résultat de l'horloge vectorielle (il reste des voisins qui n'ont pas encore reçus le message), on le retransmet en mettant notre identifiant dans le champ emmetteur/retransmetteur
\p
\si $10|\textbf{b}|a|0|S1\#a,Salon1:S2\#a,Salon2:...:SN\#a,SalonN|propagation|horloge$
%\begin{center}
%	\rotatebox{0}{\includegraphics[width=17cm]{images/retransmissionsalon.eps}}\\
%\end{center}
			\paragraph{Suppression d'un salon}
En ce qui concerne la suppression des salons qui ne sont plus à portée (on ne peut bien sur pas recevoir de message nous prévenant de cela, sauf indirectement en frontière), un autre démon s'en charge : régulièrement, il parcours la liste des salons connus et vérifie la date de dernier contact. En cas d'absence prolongée de messages, on supprime alors le salon.
			\paragraph{Présence d'un noeud dans un salon}
Afin de tenir a jour une liste des personnes connectées à un salon, même si celles-ci ne parlent pas, les noeuds broadcastent un message de présence dans ce salon à intervale régulier. Dans ce ping est aussi inséré le pseudo du noeud, pour une mise a jour en temps réel. Le fonctionnement de cette signalisation est semblable à celle des pings de salon. La forme du message envoyé est :
\p
\si $11|Salon|Noeud|PseudoDeNoeud|horloge$
\p
Ainsi, quand un noeud reçoit le signalement d'un noeud (pour un salon donné), s'il connait ce salon (dans sa zone de couverture), il le traite. Il commence donc par regarder si il avait déjà reçu ce message, dans le cas contraire, il en extrait les informations et se met à jour si nécessaire (nouveau connecté au salon, changement de pseudo,..). Enfin, il retransmet le message en cas de besoin (dans la portée et des participants qui ne l'ont pas reçu). 

		\subsubsection{Messages}
C'est cette partie du core qui va récupérer les messages en entrée et qui va les rediriger selon leur type aux autres parties du code pour qu'ils soient gérés.
\p
Elle s'occupe cependant directement de tout ce qui a directement trait à la discution, c'est à dire aux messages texte que l'utilisateur désire propager et les messages texte reçu des autres utilisateurs.
\p
Ces messages sont de la forme:
\p
\begin{center}
\begin{tabular}{lc}
	%\hline
	\textbf{Champ} & \textbf{Exemple}\\ \hline
	type de message (0=message texte) & 0\\ %\hline
	id du salon & S1\#centre\\ %\hline
	id du noeud émetteur & a\\ %\hline
	estampille & 12\\ %\hline
	horloge vectorielle & horloge\\ %\hline
	champs de gestion de la propagation & propagation\\ %\hline
	message texte & message\\
	%\hline
\end{tabular}
\end{center}
\p Ce qui donne une fois formatés:
\si $0|S1\#centre|a|horloge|propagation|message$
\p

		\subsubsection{Messages manquants}
Afin de pouvoir détecter les messages manquants, et pouvoir les retransmettre, il faut garder en mémoire l'ensembe des messages, ainsi que l'estampille associée et le couple emmetteur / numéro d'action.\\
\begin{center}
	\rotatebox{0}{\includegraphics[width=10cm]{images/histo.eps}}\\
\end{center}
\p
Lorsqu'un noeud reçoit un message contenant une horloge vectorielle il va la parcourir afin de vérifier si il lui manque des messages. Si c'est le cas, il ajoute le dit message à sa liste des message à demander aux autres participants du salon.\\
La gestion de la demande des messages manquants se fait à intervalle régulier. En effet, à chaque fois que le noeud va se signaler aux autres membres du salon, il va en profiter pour inclure dans ce message la liste de ce qu'il a raté pour y inclure sa demande, sous la forme de couples, noeud - numéros d'actions.
\p
Afin d'éviter de demander indéfiniment un message qu'aucun noeud restant dans le salon ne posèderait. Pour cela, chaque message possède un nombre de tentatives de récupèration, qui est décrémenté chaque demande. Une fois ce compteur tombé à zero, le message est supprimé de la liste et ne sera donc plus jamais demandé.
\p
Quand un noeud reçoit une demande de transmission de messages manquants, il va d'abord commencer par regarder si il possède les dits messages. Il va donc envoyer ces messages au noeud demandeur, et les retirer de la liste des demandes avant de la retransmettre.
\p
Le noeud recevra alors une partie, ou la totalité des messages manquants, eventuellement en plusieurs fois et avec des doublons. Le noeud demandeur parcours alors la liste des messages dans la réponse et les ajoute, si besoin, à sa liste, en y ajoutant un marquer afin de pouvoir les différencier.

		\subsubsection{Chronologie des messages}
	Afin d'avoir un ordre total sur les messages reçus, il a fallu ajouter un mécanisme d'estampille. A chaque message est donc associé un nombre entier, que chaque noeud incrémentera quand il en enverra un nouveau. Les noeuds synchronisent cette estampille de plusieurs façons :
\begin{itemize}
\item A la réception d'un message, on prend l'estampille associée et on la sauvegarde.
\item A la réception de signalisation de salon, ce qui permet d'avoir une estamille à jour à la connexion.
\end{itemize}
\p
On possède donc une estampille à jour qu'il nous suffira d'incrémenter avant d'envoyer notre message. Les autres noeuds la recevront et se mettront alors à jour.
\p
Cette estampille est donc utilisée à l'affichage des messages, en triant la liste des messages en fonction de cette estampille.

		\subsubsection{Voisins}
Chaque noeud possède la liste de ses voisins directs (à portée directe du périphérique de communication) qui est mise à jour gràce aux pings. Le ping est envoyé a intervalle régulier, c'est un message de type 20, il contient l'id du noeud source et la date locale d'envoi. Les noeuds le recevant y répondent avec un message de type 21 qui contient leur id, l'id du noeud ayant envoyé le ping et la date locale du noeud émetteur (récupérée dans le message reçu).
\p
Quand le noeud reçoit une réponse à son ping, il vérifie si cette réponse lui est destinée. Si oui, il extrait du message l'id du noeud ayant répondu, la date locale contenue dans le message et calcule donc la distance en temps en soustrayant ces 2 valeurs.
\p
A chaque fois que l'on envoie un ping, on parcours la liste des voisins et on regarde la dernière fois où ils ont répondu. Si ce temps est trop élévé, le voisin est supprimé.
%\p
%La liste des voisins est stockée sous forme de tableau :
%\p
%\begin{tabular}{|c|c|c|}
%	\hline
%	id du noeud &
%	distance du noeud &
%	date du dernier contact &
%	\hline
%\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Communication
	\subsection{Communication (de type stdin/stdout)}
		\subsubsection{Configuration}
Propre au choix d'interface de communication, elle positionne les entrées et sorties en mode asynchrone, non bloquantes et non bufferisées.
		\subsubsection{Builder}
Le builder permet de formater les informations à transmettre selon un format adapté au mode de communication utilisé. Dans notre cas, il s'agit de concaténer les informations séparées par des caractères spéciaux dans une seule chaine de texte.
		\subsubsection{Envoi}
L'envoi revient ici à envoyer une chaîne de caractères dans stdout.
		\subsubsection{Réception}
Comme pour l'envoi, la réception d'un message revient à récupérer les informations dans stdin.
		\subsubsection{Parser}
A l'inverse du builder, le parser transforme en tableau commun à toutes les couches communications, les chaînes de caractères reçues.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Interface
	\subsection{Interface}
	L'aide pour utiliser l'interface est accessible via la commande /help
		\subsubsection{Tile}
Une première interface a été développée en Tk pour pouvoir rapidement visualiser les développements des autres modules. Cependant, le développement d'une interface Tile était étudié en parallèle.
Les widgets Tile intègrent en fait de nouveaux widgets et une nouvelle implémentation de la plupart des widgets core Tk. De plus, Tile permet, à la différence de Tk, une gestion des thèmes. On peut ainsi donner aux fenêtres Tile une allure proche du système d'exploitation d'exécution. Tile devrait être complètement intégré dans la prochaine version de Tk (dans la version qui nous utilisons, les thèmes Windows Xp et Aqua ne sont pas disponibles). Pour une compatibilité complète avec les versions de Tk installées sur les machines susceptibles d'exécuter l'application, nous avons embarqué les widgets Tile dans notre code, l'application est plus lourde mais il n'est pas nécessaire d'installer Tile pour l'exécuter.
		\subsubsection{Gestion des 5 parties de l'interface}
Les 5 parties exposées dans la partie spécifications de l'interface sont redimensionnables dynamiquement (widget paned de Tile) en largeur et en hauteur. C'est la solution la plus simple pour permettre aux utilisateurs d'afficher ou non certaines parties de l'interface.
		\subsubsection{Liste des salons, des utilisateurs, des voisins (debug)}
Tous les affichages des listes sont gérés par des widgets tile treeview. Normalement destinés à afficher des arborescences de répertoires, les treeview permettent aussi d'afficher des listes en gérant automatiquement l'alternance des couleurs (selon les thèmes). De plus il peuvent contenir des sous-sections et des images. Nous avons donc préféré cette solution (par rapport au widget tk listbox) en imaginant qu'à l'avenir, les sous-sections pouvaient être utiles pour contenir des informations et que les images pouvaient être associées à un salon.
		\subsubsection{Une copie d'écran de l'interface (thème blue)}

\begin{center}
	\rotatebox{0}{\includegraphics[width=10cm]{images/screenshot_interface_blue.eps}}\\
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Algorithmes
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Algorithmes}
Cette section a pour but de présenter de manière formelle les différents algorithmes implémentés dans l'application de chat.\\\\
Ces algorithmes ne concernent que les actions gardées pertinentes vis à vis du sujet d'étude (l'algorithmique répartie) et ne traite pas les actions guardées purement liées à l'interface (appui sur un bouton, sélection d'une ligne\dots).\\\\
La majorité de ces algorithmes concerne l'arrivée ou l'envoi d'un message d'un type particulier sur le réseau (message de type message, ping, ping de salon...), mais certains concernent des actions guardées déclenchées à l'expiration de timers :\\
\begin{itemize}
	\item Réception d'un message \\
	\item Réception d'un ping de salon\\
	\item Réception d'un message de signalisation de connexion\\
	\item Envoi d'un ping de voisin\\
	\item Réception d'un ping de voisin\\
	\item Réception d'un message de rediffusion\\
	\item Expiration du timer de ping de salon\\
	\item Procédure d'envoi d'un ping de salon\\
\end{itemize}
\newpage

	\section{Algorithme de réception d'un message (id 0)}
\begin{verbatim}

recevoir ([msg]) de Sk
//éclate le mesage en différentes parties distinctes
 id_noeud, id_salon, estampille, horloge, noeuds, corps <-- msg
Si id_salon est inconnu
    retour
Finsi
Si on a déjà recu ce message (vérification grâce à l'horloge vectorielle)
    retour
Finsi
Mettre l'horloge vectorielle à jour avec celle que l'on vient de recevoir
Pour chaque noeud qui n'a pas encore recu ce message et qui doit le recevoir :
    envoyer([msg])
Si on est connecté au salon id_salon :
    Verifier, grace a l'horloge du noeud emmeteur, si il nous manque des messages
    Ajouter les informations contenues dans l'horloge a notre historique
    Si le corps du message n'est pas nul :
        ajouter ce message à la liste des messages
        afficher le nouveau message arrivé
    Finsi
    Ajouter, si besoin est, l'emetteur du message à la liste des connectés au salon
Finsi

\end{verbatim}

\newpage

	\section{Algorithme de réception d'un ping de salon (id 10)}
\begin{verbatim}
recevoir ([msg]) de Sk
//éclate le mesage en différentes parties distinctes
id_noeudSource, id_centre, distance, id_centreSuppleant, poidsFuturCentre , 
    listeSalons, horloge <-- msg
Si id_noeudSource n'est pas un de nos voisins :
    retour
Finsi
distanceVoisinCourant <-- distance actuelle par rapport au noeud
        émettant/relayant le ping (pas forcément le premier émetteur)
//distance totale par rapport au centre du salon, noeud ayant émit le ping
var_distance <-- distance + distanceVoisinCourant  
Pour tous les salons X incluts dans le ping :
    idSalonTmp <-- id du salon courant
    nomSalonTmp <-- nom complet du salon courant
    pingSalonTmp <-- numero de ping
    estSalonTmp <-- estampille
    Si id_centreSuppleant == notre_id :
        //on devient centre suppléant désigné par le centre
        IdCentreSuppleant(X) <-- poidsFuturCentre
    Sinon :
        Si on est centre du salon X :
            //on était centre du salon mais un autre salon est désigné
            Si IdCentreSuppleant(X) < id_centreSuppleant :
                On n'est plus centre supplléant du salon X (mais on garde notre poids)
            Finsi
        Finsi
    Finsi
    //si on a deja recu ce ping
    Si pingSalonTmp <= numero de ping du salon idSalonTmp
        passer à l'itération suivante de la boucle (continue)
    Finsi
    Mettre à jour la valeur du ping du salon idSalonTmp avec pingSalonTmp
    Si on ne connait pas encore le salon idSalonTmp :
        //on est trop loin du centre du salon 
        Si var_distance > porteeMaxSalon :
            retour
        Finsi
        Ajouter le salon idSalonTmp à la liste des salons connus
    //on connait déjà le salon	
    Sinon :
        /* on est trop loin du centre du salon, on ne retire pas tout de suite le salon trop 
         * loin en ne mettant pas à jour sa date de dernier contact, il sera supprimé 
         * par la fonction de vérification périodique des distances de centre de salon   */
        Si var_distance > porteeMaxSalon :
            passer à l'itération suivante de la boucle (continue)
        Finsi
        Mettre à jour la date de dernier contact avec ce salon
        Mettre à jour la distance avec le centre de ce salon
        Mettre à jour le numero de ping de ce salon
        Mettre à jour l'estampille de ce salon
    Finsi
    Pour chaque noeud qui n'a pas encore recu ce message et qui doit le recevoir :
        envoyer([msg])
\end{verbatim}

\newpage

	\section{Algorithme de réception d'un message de signalisation de connexion (id 11)}
\begin{verbatim}
recevoir ([msg]) de Sk
//éclate le mesage en différentes parties distinctes
id_salon, id_noeud, noeudPseudo, horloge, noeuds(marquage), messagesManquants <-- msg
// Si on ne connait pas le salon (trop loin) on ignore
Si le salon est trop loin :
    retour
Finsi
// Par defaut, on transmet la liste des messages manquants au noeud emmeteur de ping 
// sans la modifier
listeMessagesEncoreManquant <-- messagesManquants
// Le pseudo a change, on rafraichi
Si noeudPseudo != noeudPseudoPrécédent :
    mettre à jour le pseudo avec noeudPseudo
    réafficher la liste des connectés au salon
    réafficher les messages de ce salon
Finsi
Si on est connecté au salon id_salon :
    Verifier que nous n'avons pas de message manquant grace à l'horloge vectorielle reçue
    // Récuperer la liste des messages manquants au noeud 
    // emmeteur de ping et que l'on est pas en mesure d'envoyer
    listeMessagesEncoreManquant <-- messages manquants que l'on ne peut envoyer 
    Ajouter les informations contenues dans l'horloge a notre historique
    Rafraichir l'horloge vectorielle
    Ajouter le noeud emetteur (id_noeud) a la liste des connectes au salon (salonId)
Finsi
/*
 * Recupere la nouvelle liste des noeuds qui ont recu le ping
 * Ou qui le recevront (par anticipation)
 * null si il n'y a pas besoin de retransmettre
 */
ListeNoeudsARetransmettrePresence <-- liste des noeuds à qui retransmettre le message
// Renvoi le message si des personnes doivent encore le recevoir
Si ListeNoeudsARetransmettrePresence != "" :
    Envoyer(id_noeud, noeudPseudo, id_salon, horloge, 
    ListeNoeudsARetransmettrePresence, listeMessagesEncoreManquant)
Finsi
\end{verbatim}

\newpage

	\section{Algorithme d'envoi d'un ping de voisin (id 20)}
\begin{verbatim}
/*
 * notre_horloge : contient l'horloge en millisecondes de notre machine
 * notre_id : contient notre identifiant de noeud
 * delai_suppression_voisin : constante "temporelle" au delà de laquelle on supprime
 * le voisin
 */
// Envoi du ping proprement dit
envoyer ping aux voisins contenant notre_id et notre_horloge
// Recupere la liste des ids de nos voisins
var_listeVoisinsId <-- ids de nos voisins
//regarde maintenant si nos voisins sont "toujours là"
Pour chaque noeud parmis nos voisins :
    // le voisin n'a pas été vu depuis trop longtemps, il est parti, on le supprime alors
    Si notre_horloge - dernier_contact_du_noeud > delai_suppression_voisin :
        supprimer noeud
    Finsi
Finpour
\end{verbatim}
	\section{Algorithme de réception d'un ping de voisin (id 21)}
\begin{verbatim}
recevoir ([msg]) de Sk
// le ping initial vient'il de nous?
Si id_destinataire == notre_id :
    /*
     * on memorise les informations (id du noeud, date de dernier contact : maintenant,
     * distance)
     */
    ajouter le voisin d'id id_emetteur (si déja existant, pas d'ajout)
    mettre à jour la date de dernier contact de ce noeud
    // distance = (horloge_actuelle - horloge_recue_dans_ping) / 2
    mettre à jour la distance de ce noeud 
Finsi
\end{verbatim}

\newpage

	\section{Algorithme de réception d'un message de rediff (id 30)}
\begin{verbatim}
recevoir ([msg]) de Sk
//éclate le mesage en différentes parties distinctes
id_salon, id_noeud, noeuds, messages_manquants <-- msg
Si id_salon est inconnu (salon pas à portée)
    retour
Finsi
//si le message nous est destiné
Si id_noeud == notre_id :
    /*
     * on va traiter le champ messagesManquants qui contient un ensemble de messages
     * chaque noeud de liste_noeuds aura un ensemble de message liste_messages associé 
     */
    liste_noeuds, liste_messages <-- découpage de messagesManquants
    //on va itérer sur charque noeud 
    Pour chaque noeud X de liste_noeuds :
        /*
         * chaque liste_messages contient un ensemble de messages
         * chaque message contenant un numero, un contenu, une estampille
         * on va donc devoir les séparer et faire une iteration
         * sur chaque pour voir si il nous les faut
         */
        //contient l'ensemble des messages du noeud X
        liste_mess_tmp <-- liste_messages[noeud_X]
        Pour chaque numero, contenu, estampille de liste_mess_tmp :
            //nous ne gardons que les messages des salons où nous sommes connecté
            Si on est connecté au salon id_salon :
                Si on a pas déjà reçu ce message :
                    Ajouter le message "numero, contenu, estampille" à notre historique
                    Afficher message
                Finsi
            Finsi
        Finpour
    Finpour
Finsi        
//le message ne nous est pas destiné
Sinon :
    /*
     * pour déterminer si tous les noeuds qui doivent recevoir le message l'ont recu
     * on utilise le marquage du champ "noeud" que l'on a recu dans le message
     */
    Si tous les noeuds à qui le message doit etre retransmis n'ont pas recu le message :
        /*
         * on modifie noeud dans msg en ne laissant que les noeuds qui doivent 
         * encore recevoir le message, pas ceux qui l'ont deja recu
         */
        Envoyer([msg]) avec noeud modifié
    Finsi
Finsi

\end{verbatim}
\newpage
%%%
% (proc proc_verifieSalonsPing)
%%%
	\section{Timer de ping du salon X arrive à zéro }
\begin{verbatim}
/*
 * Cette procédure vérifie régulièrement les dates de dernier contact
 * de chaque centre de salon à portée pour vérifier 
 * qu'ils sont toujours présents.
 */
Pour chaque salon X connu (ie. à portée) :
    Si on n’est pas le centre :
        // le centre est parti
        Si on a pas eu de nouvelles depuis trop longtemps :
            Si on est centre suppléant potentiel (si notre poids existe) :
                //le centre suppléant demande à prendre le pouvoir
                On se nomme centre
                Envoyer un ping de salon pour indiquer que nous sommes le nouveau centre (ce ping peut être arrêté par des centres suppléants plus forts)
            Finsi 
            Retirer X de la liste des salons connus
        Finsi
    Finsi
Finpour
Réarmement du timer de ping 
\end{verbatim}
%%%
% (proc_envoiSalonsPing)
%%%

	\section{Procédure d’envoi de ping de salon}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TODO : LE REMETTRE!!!
% 
%//si on n'élit pas le même noeud comme centre secondaire on change l'Id
% Si ancienFuturCentreSalon != Proc_getFuturCentreSalon :
%		Mettre à jour IdFuturCentreSalon
% Finsi
% ...
% ( Id_du_nœud, Id_du_nœud, 0, Proc_getFuturCentreSalon, IdFuturCentreSalon,  listeSalonsPing)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{verbatim}
listeSalonsPing <-- null 
//on met dans var_listeSalonsPing la liste des salons dont on est le centre
Pour chaque salon connu :
    Si on est le centre :
       /*
        * nous sommes le centre d'un salon,
        * nous devons désigner un centre suppléant
        * en cas de deconnexion (algorithme suivant)
        */
       centreSuppléant <-- centre suppléant de ce salon
       poidsCentreSuppléant <-- poids du centre supplléant
       listeSalonsPing<--listeSalonsPing+ nom_salon+ centreSuppléant poidsCentreSuppléant
    Finsi
Finpour
//si on est le centre d'au moins un salon, on a un ping à transmettre
Si listeSalonsPing != null 
    Envoyer ping de salon 
Finsi
Réarmement du timer de ping de salon
\end{verbatim}
\newpage
\section {Algorithme de détermination des centres suppléants}
\begin{verbatim}
/*
 * Procedure déterminant le futur centre suppléant en cas de deconnexion
 * du centre principal
 *
 * liste des connectés : liste des connectés à un salon particulier
 * liste des voisins   : liste des voisins directs du noeud
 */

Si liste des connectés == null :
    Retourner notre_id
Finsi
/*
 * si aucun noeud participant au salon n'est à portée directe
 * nous n'avons pas leur distance, on en prend donc un
 * au hasard
 */
Si aucun de la liste des connectés n’est dans la liste des voisins :
    Retourner random(id de la liste des connectés sauf nous)
// sinon on retourne le noeud le plus proche de nous et qui est dans le salon
Sinon :
    Retourner id du nœud présent dans les 2 listes et dont la distance est min
Finsi
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Conclusion
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Conclusion}
Le premier constat que l'on peut tirer de ce projet est que la mise en place d'algorithmes de communication dans un réseau mouvant, à la topologie changeante et fortement dynamique peut difficilement accepter une faible utilisation du réseau et une bonne fiabilité. Cela demande au final, si ce n'est de sacrifier l'un ou l'autre, de préférer les approches pragmatiques. \\
Les algorithmes classiques utilisés dans des réseaux à topologie connue et fixe (un anneau par exemple) ne peuvent s'appliquer ici, et les solutions mises en place induisent donc une complexité supérieure.

\end{document}
